package alo.p10;

/**
 * @ClassName QuickSort
 * @Description 快速排序
 * @Author Fanxc
 * @DATE 2021/3/12 9:50
 * @Version 1.0
 */
public class QuickSort {
    void quickSort(int[] A,int low,int high){
        int pivot;
        if (high>low){
            pivot=partition(A,low,high);
            quickSort(A,low,pivot-1);
            quickSort(A,pivot+1,high);
        }
    }

    int partition(int[] A,int low,int high) {
        int left,right,temp,pivot_item=A[low];
        left=low;
        right=high;
        while (left<right){
            while (A[left]<=pivot_item&&left<high){
                left++;
            }
            while (A[right]>pivot_item&&right>low){
                right--;
            }
            if (left<right){
                temp=A[left];
                A[left]=A[right];
                A[right]=temp;
            }
        }
        A[low]=A[right];
        A[right]=pivot_item;
        return right;
    }
}
